#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// https://leetcode.cn/problems/combination-sum-ii/?envType=problem-list-v2&envId=z8Em6vKo
// 40. 组合总和 II

class Solution
{
public:
    void recursionTry(vector<vector<int>> &ans, vector<int> &candidates, int begin, int remainder, vector<int> &curSet)
    {
        if (remainder == 0)
        {
            ans.push_back(curSet);
            return;
        }
        for (int i = begin; i < candidates.size(); i++)
        {
            if (i== begin || (i > 0 && candidates[i] != candidates[i - 1]))
            {
                if (candidates[i] <= remainder)
                {
                    curSet.push_back(candidates[i]);
                    recursionTry(ans, candidates, i + 1, remainder - candidates[i], curSet);
                    curSet.pop_back();
                }
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> ans;
        vector<int> curSet;
        sort(candidates.begin(), candidates.end());
        recursionTry(ans, candidates, 0, target, curSet);
        return ans;
    }
};

int main()
{
    return 0;
}